10104 - Euclid Problem/p10104.cpp

   1 #include <iostream>
   2 #include <math.h>
   3 using namespace std;
   4
   5 long long gcd(long long p, long long q, long long *x, long long *y){
   6   long long x1, y1;
   7   long long g;
   8
   9   if (q>p) return(gcd(q,p,y,x));
  10   if (q == 0){
  11     *x = 1;
  12     *y = 0;
  13     return p;
  14   }
  15   g = gcd(q, p%q, &x1, &y1);
  16   *x = y1;
  17   *y = (x1 - floor(p/q)*y1);
  18   return g;
  19 }
  20
  21 int main(){
  22   long long a, b, x, y, d, k;
  23   while (cin >> a >> b){
  24
  25     d = gcd(a,b,&x,&y);
  26     cout << x << " " << y << " " << d << endl;
  27     //cout << d << endl;
  28     //bool found = false;
  29     //for (y=1; !found; ++y){
  30       /*x = 0;
  31       do{
  32         k = a*x + b*y;
  33         --x;
  34         }while(k > d);
  35
  36       if (k == d){
  37         found = true;
  38         ++x;
  39         --y;
  40         }*/
  41       //double c = 1.0*(d - b*y)/a;
  42       //cout << "c es: " << c << endl;
  43       //if (c == floor(c)){ //es entero
  44     //found = true;
  45     //x = (long long)c;
  46     //--y;
  47     //}
  48     //}
  49
  50     //cout << x << " " << y << " " << d << endl;
  51     //printf("%lld %lld %lld\n", x, y, d);
  52
  53
  54   }
  55   return 0;
  56 }